Time series data can be generated and analyzed for a number of applications. For example, automatic equipment monitoring can avoid costly repairs of industrial equipment. This can be done by analyzing time series data acquired by sensors on or near the equipment to detect anomalies that may indicate that maintenance or repair of the equipment is needed.
Therefore, it is desired to efficiently learn a model of one-dimensional time series data. Then, the model can be used to detect anomalies in future testing time series data from the same source. Typically, the model is learned from a training time series without anomalies.
A number of methods for learning models of time series data are known. A simple and effective method uses the entire training time series data as the model. In other words, the entire training time series is stored as the model. Hence, the time to train is negligible. To detect anomalies, each window of the testing time series is compared to every window of the training time series, and a distance to a nearest matching window is used as an anomaly score. If the anomaly score is above a threshold, then an anomaly is signaled, see Keogh et al., “HOT SAX: Finding the Model Unusual Time Series Subsequence: Algorithms and Applications,” ICDM 2005. The main drawback of that approach is that it requires storing the entire training time series, which may be very large, and the computation of the anomaly scores is slow, which may preclude using that method for real-time applications, and with a wide range of different types of time series data.
Another class of methods for modeling time series data uses predictive techniques. Such methods use a number of previous values of the time series data to predict a current value, see Ma et al., “Online Novelty Detection on Temporal Sequences,” SIGKDD 2003, and Koskivaara, “Artificial Neural Networks for Predicting Patterns in Auditing Monthly Balances, J. of the Operational Research Society, 1996.) Although those predictive models can be compact, the models may not accurately predict some time series data.
Another method for modeling time series data is as a trajectory through a d-dimensional feature space. Piecewise linear paths or boxes in the d-dimensional space have been used to efficiently represent valid paths in the training time series data, see Mahoney et al., “Trajectory Boundary Modeling of Time Series for Anomaly Detection,” Workshop on Data Mining Methods for Anomaly Detection at KDD, 2005. That method for learning has a complexity of O(nlogn).
A slightly different approach determines a subspace for representing short windows of time series data, and then models trajectories in the subspace with an autoregressive model or a density estimation, see Liu et al., “Modeling Heterogeneous Time Series Dynamics to Profile Big Sensor Data in Complex Physical Systems,” IEEE Conf. on Big Data, 2013.
U.S. patent application Ser. No. 13/932,238, Method for Detecting Anomalies in a Time Series Data with Trajectory and Stochastic Components,” filed by Jones et al. on Jul. 1, 2013 describes a method to detect anomalies in time series data by comparing universal features extracted from testing time series data with the universal features acquired from training time series data to determine a score. The universal features characterize trajectory components of the time series data and stochastic components of the time series data. Then, an anomaly is detected if the anomaly score is above a threshold. A method for efficiently learning a set of universal features (which are a type of exemplar) from training time series is not disclosed in that patent application.
Therefore, there is a need to efficiently learn accurate and compact models for time series that can be applied to many different types of time series data.